package demo6;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/*
        学生选课系统  优先满足修满本学期学分 再考虑课程优先级  利用贪心策略
 */

public class CourseSchedulerAdvanced {
    static class Course {
        String name;
        int startTime;
        int endTime;
        int credits;
        int difficulty;
        double priority; // 优先级 = (学分 * 10) / (难度 * 时间)
        ArrayList<String> prerequisites; // 课程的前置课程

        Course(String name, int startTime, int endTime, int credits, int difficulty, ArrayList<String> prerequisites) {
            this.name = name;
            this.startTime = startTime;
            this.endTime = endTime;
            this.credits = credits;
            this.difficulty = difficulty;
            this.prerequisites = prerequisites;
            this.priority = (double) (credits * 10) / (difficulty * (endTime - startTime));
        }
    }

    // 检查课程是否与当前课程表兼容
    private static boolean isCompatible(ArrayList<Course> schedule, Course newCourse) {
        for (Course c : schedule) {
            if (newCourse.startTime < c.endTime && newCourse.endTime > c.startTime) {
                return false; // 时间冲突
            }
        }
        return true;
    }

    // 计算总学分
    private static int calculateTotalCredits(ArrayList<Course> schedule) {
        int total = 0;
        for (Course c : schedule) {
            total += c.credits;
        }
        return total;
    }

    // 判断是否可以选这门课程（前置课程判断）
    private static boolean canTakeCourse(ArrayList<Course> schedule, Course newCourse) {
        for (String prereq : newCourse.prerequisites) {
            boolean prerequisiteMet = false;
            for (Course c : schedule) {
                if (c.name.equals(prereq)) {
                    prerequisiteMet = true;
                    break;
                }
            }
            if (!prerequisiteMet) {
                return false; // 如果前置课程没有修读，则不能选该课程
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("欢迎使用课程表安排系统！");
        System.out.println("本系统将选择课程满足学分要求，并优化优先级（(学分*10)/(难度*时间））。");

        // 输入目标学分
        System.out.print("请输入这学期需要修满的最低学分: ");
        int targetCredits = scanner.nextInt();
        scanner.nextLine();

        // 输入课程数量
        System.out.print("请输入课程数量 n: ");
        int n = scanner.nextInt();
        scanner.nextLine();

        // 存储所有课程
        Course[] courses = new Course[n];
        System.out.println("请依次输入每门课程的详细信息：");
        for (int i = 0; i < n; i++) {
            System.out.println("课程 " + (i + 1) + ":");
            System.out.print("课程名称: ");
            String name = scanner.nextLine();
            System.out.print("开始时间: ");
            int start = scanner.nextInt();
            System.out.print("结束时间: ");
            int end = scanner.nextInt();
            System.out.print("学分 (1-5): ");
            int credits = scanner.nextInt();
            System.out.print("难度 (1-5): ");
            int difficulty = scanner.nextInt();
            scanner.nextLine();

            System.out.print("请输入该课程的前置课程名称（若无，请输入'none'）：");
            String prereqInput = scanner.nextLine();
            ArrayList<String> prerequisites = new ArrayList<>();
            if (!prereqInput.equalsIgnoreCase("none")) {
                prerequisites.add(prereqInput);
            }

            courses[i] = new Course(name, start, end, credits, difficulty, prerequisites);
        }

        // 按结束时间排序
        Arrays.sort(courses, Comparator.comparingInt(c -> c.endTime));

        ArrayList<Course> schedule = new ArrayList<>();
        int lastEndTime = 0; // 从最早时间开始
        int totalCredits = 0;

        for (Course current : courses) {
            if (current.startTime >= lastEndTime && canTakeCourse(schedule, current)) {
                schedule.add(current);
                lastEndTime = current.endTime;
                totalCredits += current.credits;
                if (totalCredits >= targetCredits) break;
            }
        }

        // 如果学分未达标，提示用户
        if (totalCredits < targetCredits) {
            System.out.println("警告：第一阶段未达到目标学分，将尝试优化调整。");
        }

        // 第二阶段：优化优先级
        Arrays.sort(courses, Comparator.comparingDouble(c -> -c.priority)); // 按优先级降序
        for (Course current : courses) {
            if (!schedule.contains(current)) {
                ArrayList<Course> tempSchedule = new ArrayList<>(schedule);
                int tempCredits = totalCredits;

                // 移除所有冲突且优先级较低的课程
                for (int j = tempSchedule.size() - 1; j >= 0; j--) {
                    Course existing = tempSchedule.get(j);
                    if (existing.endTime > current.startTime && // 时间冲突
                            existing.startTime < current.endTime &&
                            current.priority > existing.priority && // 优先级更高
                            canTakeCourse(tempSchedule, current)) { // 前置课程要求满足
                        tempCredits -= existing.credits;
                        tempSchedule.remove(j);
                    }
                }

                // 学分仍达标且时间兼容，加入新课程
                if (tempCredits + current.credits >= targetCredits && isCompatible(tempSchedule, current)) {
                    tempSchedule.add(current);
                    schedule = tempSchedule;
                    totalCredits = tempCredits + current.credits;
                    lastEndTime = Math.max(lastEndTime, current.endTime);
                }
            }
        }

        // 输出结果
        System.out.println("\n优化后的课程表如下：");
        System.out.println("课程名称\t开始时间\t结束时间\t学分\t难度\t优先级");
        System.out.println("--------------------------------------------------");
        schedule.sort(Comparator.comparingInt(c -> c.startTime)); // 按开始时间排序输出
        for (Course c : schedule) {
            System.out.printf("%s\t\t%d\t\t%d\t\t%d\t\t%d\t\t%.3f%n",
                    c.name, c.startTime, c.endTime, c.credits, c.difficulty, c.priority);
        }
        System.out.println("共安排了 " + schedule.size() + " 门课程，总学分：" + totalCredits);
        if (totalCredits >= targetCredits) {
            System.out.println("恭喜！总学分达到目标：" + targetCredits);
        } else {
            System.out.println("抱歉，无法安排足够的课程达到目标学分 " + targetCredits + "，请检查输入课程！");
        }

        scanner.close();
    }
}
